Bit Manipulation
Table of Contents
- Bit Manipulation Fundamentals
- Pattern 1: Basic Bitwise Operations
- Pattern 2: Bit Checking & Setting
- Pattern 3: Power of Two Operations
- Pattern 4: Single Number Problems
- Pattern 5: Bit Counting & Manipulation
- Pattern 6: Bitmasking Techniques
- Pattern 7: XOR-Based Problems
- Pattern 8: Bit Shifting Patterns
- Pattern 9: Gray Code & Binary Representation
- Pattern 10: Advanced Bit Manipulation
- Pattern 11: Optimization with Bits
- Pattern 12: Real-World Applications
Bit Manipulation Fundamentals
Core Concepts and Operations
// Basic Bitwise Operations in Java
public class BitManipulationFundamentals {
// Bitwise Operators
public static void demonstrateBitwiseOperators() {
int a = 12; // Binary: 1100
int b = 10; // Binary: 1010
System.out.println("a = " + a + " (Binary: " + Integer.toBinaryString(a) + ")");
System.out.println("b = " + b + " (Binary: " + Integer.toBinaryString(b) + ")");
// AND operator (&)
int andResult = a & b; // 1100 & 1010 = 1000 (8)
System.out.println("a & b = " + andResult + " (Binary: " + Integer.toBinaryString(andResult) + ")");
// OR operator (|)
int orResult = a | b; // 1100 | 1010 = 1110 (14)
System.out.println("a | b = " + orResult + " (Binary: " + Integer.toBinaryString(orResult) + ")");
// XOR operator (^)
int xorResult = a ^ b; // 1100 ^ 1010 = 0110 (6)
System.out.println("a ^ b = " + xorResult + " (Binary: " + Integer.toBinaryString(xorResult) + ")");
// NOT operator (~) - Bitwise complement
int notA = ~a; // ~1100 = ...11110011 (two's complement)
System.out.println("~a = " + notA + " (Binary: " + Integer.toBinaryString(notA) + ")");
// Left shift (<<)
int leftShift = a << 2; // 1100 << 2 = 110000 (48)
System.out.println("a << 2 = " + leftShift + " (Binary: " + Integer.toBinaryString(leftShift) + ")");
// Right shift (>>)
int rightShift = a >> 2; // 1100 >> 2 = 11 (3)
System.out.println("a >> 2 = " + rightShift + " (Binary: " + Integer.toBinaryString(rightShift) + ")");
// Unsigned right shift (>>>)
int unsignedRightShift = a >>> 2;
System.out.println("a >>> 2 = " + unsignedRightShift + " (Binary: " + Integer.toBinaryString(unsignedRightShift) + ")");
}
// Essential Bit Manipulation Utilities
public static class BitUtils {
// Get bit at position i (0-indexed from right)
public static boolean getBit(int num, int i) {
return (num & (1 << i)) != 0;
}
// Set bit at position i
public static int setBit(int num, int i) {
return num | (1 << i);
}
// Clear bit at position i
public static int clearBit(int num, int i) {
return num & ~(1 << i);
}
// Toggle bit at position i
public static int toggleBit(int num, int i) {
return num ^ (1 << i);
}
// Count number of set bits (1s)
public static int countSetBits(int num) {
int count = 0;
while (num != 0) {
count++;
num &= (num - 1); // Remove rightmost set bit
}
return count;
}
// Count number of set bits using built-in method
public static int countSetBitsBuiltIn(int num) {
return Integer.bitCount(num);
}
// Find rightmost set bit position (1-indexed)
public static int rightmostSetBit(int num) {
if (num == 0) return 0;
return Integer.numberOfTrailingZeros(num) + 1;
}
// Find leftmost set bit position (1-indexed from right)
public static int leftmostSetBit(int num) {
if (num == 0) return 0;
return 32 - Integer.numberOfLeadingZeros(num);
}
// Isolate rightmost set bit
public static int isolateRightmostSetBit(int num) {
return num & (-num);
}
// Remove rightmost set bit
public static int removeRightmostSetBit(int num) {
return num & (num - 1);
}
// Check if number is power of 2
public static boolean isPowerOfTwo(int num) {
return num > 0 && (num & (num - 1)) == 0;
}
// Reverse bits of a 32-bit integer
public static int reverseBits(int num) {
int result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (num & 1);
num >>= 1;
}
return result;
}
// Check if bits are in alternating pattern
public static boolean hasAlternatingBits(int num) {
int xor = num ^ (num >> 1);
return (xor & (xor + 1)) == 0;
}
// Swap two numbers without using temporary variable
public static void swapNumbers(int a, int b) {
System.out.println("Before swap: a = " + a + ", b = " + b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("After swap: a = " + a + ", b = " + b);
}
}
// Binary representation utilities
public static class BinaryUtils {
// Convert decimal to binary string
public static String decimalToBinary(int num) {
return Integer.toBinaryString(num);
}
// Convert binary string to decimal
public static int binaryToDecimal(String binary) {
return Integer.parseInt(binary, 2);
}
// Print binary representation with fixed width
public static void printBinary(int num, int width) {
String binary = Integer.toBinaryString(num);
String formatted = String.format("%" + width + "s", binary).replace(' ', '0');
System.out.println(num + " -> " + formatted);
}
// Get binary representation of negative numbers (two's complement)
public static String getBinaryWithSign(int num) {
if (num >= 0) {
return Integer.toBinaryString(num);
} else {
// For negative numbers, show 32-bit two's complement
return String.format("%32s", Integer.toBinaryString(num)).replace(' ', '1');
}
}
}
}
Pattern 1: Basic Bitwise Operations
1.1 Fundamental Bit Operations
// Basic bit manipulation operations
public class BasicBitOperations {
// Check if a bit is set at position i
public boolean isBitSet(int num, int position) {
return (num & (1 << position)) != 0;
}
// Set a bit at position i
public int setBit(int num, int position) {
return num | (1 << position);
}
// Clear a bit at position i
public int clearBit(int num, int position) {
int mask = ~(1 << position);
return num & mask;
}
// Toggle a bit at position i
public int toggleBit(int num, int position) {
return num ^ (1 << position);
}
// Update bit at position i with given value (0 or 1)
public int updateBit(int num, int position, boolean bitValue) {
int value = bitValue ? 1 : 0;
int mask = ~(1 << position); // Clear the bit at position
return (num & mask) | (value << position); // Set new value
}
// Get range of bits from position i to j (inclusive)
public int getBitRange(int num, int i, int j) {
// Create mask with 1s from position i to j
int allOnes = ~0; // All 1s
int left = allOnes << (j + 1);
int right = (1 << i) - 1;
int mask = left | right;
return (num & ~mask) >> i;
}
// Set range of bits from position i to j with given value
public int setBitRange(int num, int value, int i, int j) {
// Clear bits from i to j
int allOnes = ~0;
int left = allOnes << (j + 1);
int right = (1 << i) - 1;
int mask = left | right;
int cleared = num & mask;
return cleared | (value << i);
}
// Count consecutive 1s from right
public int countTrailingOnes(int num) {
int count = 0;
while ((num & 1) == 1) {
count++;
num >>= 1;
}
return count;
}
// Count consecutive 0s from right
public int countTrailingZeros(int num) {
if (num == 0) return 32; // All bits are 0
int count = 0;
while ((num & 1) == 0) {
count++;
num >>= 1;
}
return count;
}
// Find position of rightmost set bit (1-indexed)
public int findRightmostSetBit(int num) {
if (num == 0) return -1;
// Method 1: Using loop
int position = 1;
while ((num & 1) == 0) {
num >>= 1;
position++;
}
return position;
}
// Alternative method using bit manipulation trick
public int findRightmostSetBitOptimized(int num) {
if (num == 0) return -1;
// Isolate rightmost set bit and count trailing zeros
return Integer.numberOfTrailingZeros(num & -num) + 1;
}
// Check if only one bit is set (power of 2)
public boolean hasOnlyOneBitSet(int num) {
return num > 0 && (num & (num - 1)) == 0;
}
// Count number of different bits between two numbers
public int countDifferentBits(int a, int b) {
int xor = a ^ b;
return Integer.bitCount(xor);
}
}
1.2 Advanced Bit Checking
// Advanced bit checking operations
public class AdvancedBitChecking {
// Check if number has alternating bits (101010... pattern)
public boolean hasAlternatingBits(int n) {
// XOR with right-shifted version should give all 1s
int xor = n ^ (n >> 1);
return (xor & (xor + 1)) == 0;
}
// Check if all bits in given range are set
public boolean areAllBitsSetInRange(int num, int left, int right) {
// Create mask with 1s from left to right
int len = right - left + 1;
int mask = ((1 << len) - 1) << left;
return (num & mask) == mask;
}
// Check if any bit in given range is set
public boolean isAnyBitSetInRange(int num, int left, int right) {
int len = right - left + 1;
int mask = ((1 << len) - 1) << left;
return (num & mask) != 0;
}
// Find first set bit position from left (MSB side)
public int findFirstSetBitFromLeft(int num) {
if (num == 0) return -1;
return 32 - Integer.numberOfLeadingZeros(num);
}
// Check if bits form a palindrome
public boolean areBitsPalindrome(int num) {
// Get significant bits only
int significantBits = 32 - Integer.numberOfLeadingZeros(num);
for (int i = 0; i < significantBits / 2; i++) {
int leftBit = (num >> (significantBits - 1 - i)) & 1;
int rightBit = (num >> i) & 1;
if (leftBit != rightBit) {
return false;
}
}
return true;
}
// Check if number is sparse (no two adjacent bits are set)
public boolean isSparseNumber(int num) {
return (num & (num >> 1)) == 0;
}
// Find next sparse number
public int nextSparseNumber(int num) {
num++;
while (!isSparseNumber(num)) {
num++;
}
return num;
}
// Check if bit pattern matches given pattern with wildcards
public boolean matchesPattern(int num, String pattern) {
// Pattern can contain '0', '1', or 'X' (wildcard)
if (pattern.length() > 32) return false;
for (int i = 0; i < pattern.length(); i++) {
char expected = pattern.charAt(pattern.length() - 1 - i);
if (expected == 'X') continue;
int actualBit = (num >> i) & 1;
int expectedBit = expected - '0';
if (actualBit != expectedBit) {
return false;
}
}
return true;
}
}
Pattern 2: Bit Checking & Setting
2.1 Bit Manipulation for Arrays
// Bit manipulation operations on arrays
public class ArrayBitOperations {
// Find element that appears odd number of times
public int findOddOccurrence(int[] arr) {
int result = 0;
for (int num : arr) {
result ^= num;
}
return result; // XOR of all elements cancels out even occurrences
}
// Find two elements that appear odd number of times
public int[] findTwoOddOccurrences(int[] arr) {
int xor = 0;
// XOR all elements
for (int num : arr) {
xor ^= num;
}
// Find rightmost set bit in XOR
int rightmostSetBit = xor & (-xor);
int first = 0, second = 0;
// Divide numbers into two groups based on rightmost set bit
for (int num : arr) {
if ((num & rightmostSetBit) != 0) {
first ^= num;
} else {
second ^= num;
}
}
return new int[]{first, second};
}
// Check if array can be divided into pairs with equal XOR
public boolean canDivideIntoPairs(int[] arr) {
int xor = 0;
for (int num : arr) {
xor ^= num;
}
return xor == 0; // Total XOR should be 0
}
// Find minimum XOR pair in array
public int minXORPair(int[] arr) {
Arrays.sort(arr); // Sort to minimize XOR between adjacent elements
int minXOR = Integer.MAX_VALUE;
for (int i = 0; i < arr.length - 1; i++) {
minXOR = Math.min(minXOR, arr[i] ^ arr[i + 1]);
}
return minXOR;
}
// Count pairs with given XOR
public int countPairsWithXOR(int[] arr, int k) {
Set<Integer> seen = new HashSet<>();
int count = 0;
for (int num : arr) {
if (seen.contains(num ^ k)) {
count++;
}
seen.add(num);
}
return count;
}
// Find subarray with maximum XOR
public int maxSubarrayXOR(int[] arr) {
int maxXOR = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
int currentXOR = 0;
for (int j = i; j < arr.length; j++) {
currentXOR ^= arr[j];
maxXOR = Math.max(maxXOR, currentXOR);
}
}
return maxXOR;
}
// Count subarrays with XOR equal to k
public int countSubarraysWithXOR(int[] arr, int k) {
Map<Integer, Integer> prefixXORCount = new HashMap<>();
prefixXORCount.put(0, 1); // Empty prefix
int currentXOR = 0;
int count = 0;
for (int num : arr) {
currentXOR ^= num;
// Check if there exists a prefix with XOR = currentXOR ^ k
if (prefixXORCount.containsKey(currentXOR ^ k)) {
count += prefixXORCount.get(currentXOR ^ k);
}
prefixXORCount.put(currentXOR, prefixXORCount.getOrDefault(currentXOR, 0) + 1);
}
return count;
}
}
Pattern 3: Power of Two Operations
3.1 Power of Two Detection and Manipulation
// Power of two related operations
public class PowerOfTwoOperations {
// Check if number is power of 2
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// Find next power of 2 greater than or equal to n
public int nextPowerOfTwo(int n) {
if (n <= 0) return 1;
if (isPowerOfTwo(n)) return n;
// Set all bits after MSB
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n + 1;
}
// Find previous power of 2 less than or equal to n
public int previousPowerOfTwo(int n) {
if (n <= 0) return 0;
// Find position of MSB
return 1 << (31 - Integer.numberOfLeadingZeros(n));
}
// Check if number is power of 4
public boolean isPowerOfFour(int n) {
// Must be power of 2 and have set bit at even position
return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}
// Count powers of 2 less than n
public int countPowersOfTwo(int n) {
if (n <= 1) return 0;
return 32 - Integer.numberOfLeadingZeros(n - 1);
}
// Find largest power of 2 divisor
public int largestPowerOfTwoDivisor(int n) {
return n & (-n); // Isolates rightmost set bit
}
// Multiply by power of 2 using bit shifting
public int multiplyByPowerOfTwo(int num, int power) {
return num << power; // num * (2^power)
}
// Divide by power of 2 using bit shifting
public int divideByPowerOfTwo(int num, int power) {
return num >> power; // num / (2^power)
}
// Check if division by power of 2 is exact
public boolean isDivisibleByPowerOfTwo(int num, int power) {
int divisor = 1 << power;
return (num & (divisor - 1)) == 0;
}
// Round up to nearest power of 2
public int roundUpToPowerOfTwo(int n) {
if (n <= 1) return 1;
return nextPowerOfTwo(n);
}
// Round down to nearest power of 2
public int roundDownToPowerOfTwo(int n) {
if (n <= 0) return 0;
return previousPowerOfTwo(n);
}
}
3.2 Advanced Power Operations
// Advanced power-related bit operations
public class AdvancedPowerOperations {
// Fast exponentiation using bit manipulation (a^b)
public long fastPower(long base, int exponent) {
long result = 1;
while (exponent > 0) {
// If exponent is odd, multiply result with base
if ((exponent & 1) == 1) {
result *= base;
}
// Square the base and divide exponent by 2
base *= base;
exponent >>= 1;
}
return result;
}
// Fast exponentiation with modulo
public long fastPowerMod(long base, int exponent, long mod) {
long result = 1;
base %= mod;
while (exponent > 0) {
if ((exponent & 1) == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exponent >>= 1;
}
return result;
}
// Check if number can be expressed as sum of two powers of 2
public boolean isSumOfTwoPowersOfTwo(int n) {
// Try all powers of 2 less than n
for (int i = 0; (1 << i) < n; i++) {
int powerOfTwo = 1 << i;
int remaining = n - powerOfTwo;
if (isPowerOfTwo(remaining)) {
return true;
}
}
return false;
}
// Find minimum operations to reach target using doubling
public int minOperationsToReach(int start, int target) {
if (start >= target) return start - target;
int operations = 0;
while (start < target) {
if (target % 2 == 1) {
target++;
operations++;
} else {
target /= 2;
operations++;
}
}
return operations + start - target;
}
// Count set bits in all numbers from 1 to n
public int countSetBitsInRange(int n) {
int count = 0;
// For each bit position
for (int i = 0; i < 32; i++) {
int cycleLength = 1 << (i + 1);
int completeCycles = (n + 1) / cycleLength;
int remainder = (n + 1) % cycleLength;
count += completeCycles * (1 << i);
if (remainder > (1 << i)) {
count += remainder - (1 << i);
}
}
return count;
}
}
Pattern 4: Single Number Problems
4.1 Finding Unique Elements
// Single number pattern problems
public class SingleNumberProblems {
// Single Number I: Find element that appears once (others appear twice)
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
// Single Number II: Find element that appears once (others appear thrice)
public int singleNumberII(int[] nums) {
int ones = 0, twos = 0;
for (int num : nums) {
// Update twos with bits that appear twice
twos |= ones & num;
// Update ones with bits that appear once
ones ^= num;
// Remove bits that appear three times
int threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
// Alternative approach for Single Number II using bit counting
public int singleNumberIIAlternative(int[] nums) {
int result = 0;
// Check each bit position
for (int i = 0; i < 32; i++) {
int count = 0;
// Count occurrences of bit i
for (int num : nums) {
if ((num & (1 << i)) != 0) {
count++;
}
}
// If count is not divisible by 3, set this bit in result
if (count % 3 != 0) {
result |= (1 << i);
}
}
return result;
}
// Single Number III: Find two elements that appear once (others appear twice)
public int[] singleNumberIII(int[] nums) {
int xor = 0;
// XOR all numbers
for (int num : nums) {
xor ^= num;
}
// Find rightmost set bit
int rightmostSetBit = xor & (-xor);
int[] result = new int[2];
// Divide numbers into two groups
for (int num : nums) {
if ((num & rightmostSetBit) == 0) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
return result;
}
// Find element that appears k times while others appear m times
public int singleNumberGeneral(int[] nums, int k, int m) {
int[] bitCount = new int[32];
// Count bits at each position
for (int num : nums) {
for (int i = 0; i < 32; i++) {
if ((num & (1 << i)) != 0) {
bitCount[i]++;
}
}
}
int result = 0;
for (int i = 0; i < 32; i++) {
if (bitCount[i] % m == k) {
result |= (1 << i);
}
}
return result;
}
// Find missing number in array [0, n]
public int missingNumber(int[] nums) {
int n = nums.length;
int expectedXOR = 0;
int actualXOR = 0;
// XOR of all numbers from 0 to n
for (int i = 0; i <= n; i++) {
expectedXOR ^= i;
}
// XOR of all numbers in array
for (int num : nums) {
actualXOR ^= num;
}
return expectedXOR ^ actualXOR;
}
// Alternative missing number using sum difference
public int missingNumberSum(int[] nums) {
int n = nums.length;
int expectedSum = n * (n + 1) / 2;
int actualSum = 0;
for (int num : nums) {
actualSum += num;
}
return expectedSum - actualSum;
}
// Find duplicate number using bit manipulation
public int findDuplicate(int[] nums) {
int n = nums.length - 1;
// Count bits at each position
int[] bitCount = new int[32];
for (int num : nums) {
for (int i = 0; i < 32; i++) {
if ((num & (1 << i)) != 0) {
bitCount[i]++;
}
}
}
// Count expected bits for range [1, n]
int[] expectedBitCount = new int[32];
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 32; j++) {
if ((i & (1 << j)) != 0) {
expectedBitCount[j]++;
}
}
}
int result = 0;
for (int i = 0; i < 32; i++) {
if (bitCount[i] > expectedBitCount[i]) {
result |= (1 << i);
}
}
return result;
}
}
Pattern 5: Bit Counting & Manipulation
5.1 Counting Set Bits
// Bit counting operations
public class BitCountingOperations {
// Count set bits (Hamming weight) - Brian Kernighan's algorithm
public int countSetBits(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // Remove rightmost set bit
count++;
}
return count;
}
// Count set bits using built-in method
public int countSetBitsBuiltIn(int n) {
return Integer.bitCount(n);
}
// Count set bits using lookup table
private static final int[] BIT_COUNT_TABLE = new int[256];
static {
for (int i = 0; i < 256; i++) {
BIT_COUNT_TABLE[i] = (i & 1) + BIT_COUNT_TABLE[i >> 1];
}
}
public int countSetBitsLookup(int n) {
return BIT_COUNT_TABLE[n & 0xFF] +
BIT_COUNT_TABLE[(n >> 8) & 0xFF] +
BIT_COUNT_TABLE[(n >> 16) & 0xFF] +
BIT_COUNT_TABLE[(n >> 24) & 0xFF];
}
// Count total set bits from 1 to n
public int countSetBitsInRange(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
// Calculate pattern for bit i
int cycleLength = 1 << (i + 1);
int completeCycles = (n + 1) / cycleLength;
int remainder = (n + 1) % cycleLength;
count += completeCycles * (1 << i);
if (remainder > (1 << i)) {
count += remainder - (1 << i);
}
}
return count;
}
// Count numbers with even number of set bits in range [1, n]
public int countEvenSetBitNumbers(int n) {
// For large ranges, approximately half have even set bits
// For exact count, we need to iterate
int count = 0;
for (int i = 1; i <= n; i++) {
if (countSetBits(i) % 2 == 0) {
count++;
}
}
return count;
}
// Find number with maximum set bits in given range
public int maxSetBitsInRange(int left, int right) {
int max = 0;
int result = left;
for (int i = left; i <= right; i++) {
int setBits = countSetBits(i);
if (setBits > max) {
max = setBits;
result = i;
}
}
return result;
}
// Check if count of set bits is prime
public boolean hasSetBitCountPrime(int n) {
int count = countSetBits(n);
return isPrime(count);
}
private boolean isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// Count numbers with exactly k set bits in range [1, n]
public int countNumbersWithKSetBits(int n, int k) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (countSetBits(i) == k) {
count++;
}
}
return count;
}
// Generate next number with same number of set bits
public int nextNumberWithSameSetBits(int n) {
int c = n;
int c0 = 0; // Count of trailing zeros
int c1 = 0; // Count of ones after trailing zeros
// Count trailing zeros
while (((c & 1) == 0) && (c != 0)) {
c0++;
c >>= 1;
}
// Count ones after trailing zeros
while ((c & 1) == 1) {
c1++;
c >>= 1;
}
// If c0 + c1 == 31 or c0 + c1 == 0, then no bigger number exists
if (c0 + c1 == 31 || c0 + c1 == 0) {
return -1;
}
int pos = c0 + c1; // Position of rightmost non-trailing zero
n |= (1 << pos); // Flip the rightmost non-trailing zero
n &= ~((1 << pos) - 1); // Clear all bits to the right of pos
n |= (1 << (c1 - 1)) - 1; // Insert (c1-1) ones on the right
return n;
}
}
5.2 Bit Manipulation Tricks
// Advanced bit manipulation tricks
public class BitManipulationTricks {
// Isolate rightmost set bit
public int isolateRightmostSetBit(int n) {
return n & (-n);
}
// Remove rightmost set bit
public int removeRightmostSetBit(int n) {
return n & (n - 1);
}
// Isolate rightmost 0 bit
public int isolateRightmostZeroBit(int n) {
return ~n & (n + 1);
}
// Set rightmost 0 bit
public int setRightmostZeroBit(int n) {
return n | (n + 1);
}
// Check if number has adjacent set bits
public boolean hasAdjacentSetBits(int n) {
return (n & (n << 1)) != 0;
}
// Swap bits at positions i and j
public int swapBits(int n, int i, int j) {
// Check if bits are different
if (((n >> i) & 1) != ((n >> j) & 1)) {
// Swap by toggling both bits
n ^= (1 << i) | (1 << j);
}
return n;
}
// Reverse bits in a number
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>= 1;
}
return result;
}
// Fast way to reverse bits using lookup table
private static final int[] REVERSE_TABLE = new int[256];
static {
for (int i = 0; i < 256; i++) {
int reversed = 0;
int temp = i;
for (int j = 0; j < 8; j++) {
reversed = (reversed << 1) | (temp & 1);
temp >>= 1;
}
REVERSE_TABLE[i] = reversed;
}
}
public int reverseBitsFast(int n) {
return (REVERSE_TABLE[n & 0xFF] << 24) |
(REVERSE_TABLE[(n >> 8) & 0xFF] << 16) |
(REVERSE_TABLE[(n >> 16) & 0xFF] << 8) |
(REVERSE_TABLE[(n >> 24) & 0xFF]);
}
// Count leading zeros
public int countLeadingZeros(int n) {
if (n == 0) return 32;
int count = 0;
if ((n & 0xFFFF0000) == 0) { count += 16; n <<= 16; }
if ((n & 0xFF000000) == 0) { count += 8; n <<= 8; }
if ((n & 0xF0000000) == 0) { count += 4; n <<= 4; }
if ((n & 0xC0000000) == 0) { count += 2; n <<= 2; }
if ((n & 0x80000000) == 0) { count += 1; }
return count;
}
// Count trailing zeros
public int countTrailingZeros(int n) {
if (n == 0) return 32;
int count = 0;
if ((n & 0x0000FFFF) == 0) { count += 16; n >>= 16; }
if ((n & 0x000000FF) == 0) { count += 8; n >>= 8; }
if ((n & 0x0000000F) == 0) { count += 4; n >>= 4; }
if ((n & 0x00000003) == 0) { count += 2; n >>= 2; }
if ((n & 0x00000001) == 0) { count += 1; }
return count;
}
// Check if number is palindrome in binary
public boolean isBinaryPalindrome(int n) {
// Find number of significant bits
int bits = 32 - Integer.numberOfLeadingZeros(n);
for (int i = 0; i < bits / 2; i++) {
int leftBit = (n >> (bits - 1 - i)) & 1;
int rightBit = (n >> i) & 1;
if (leftBit != rightBit) {
return false;
}
}
return true;
}
// Generate all subsets using bit manipulation
public List<List<Integer>> generateSubsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
int n = nums.length;
// Generate all 2^n subsets
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(nums[i]);
}
}
subsets.add(subset);
}
return subsets;
}
}
Pattern 6: Bitmasking Techniques[6]
6.1 Basic Bitmasking
// Bitmasking techniques for state representation
public class BitwaskingTechniques {
// Check if subset represented by mask has target sum
public boolean hasSubsetSum(int[] arr, int mask, int targetSum) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
if ((mask & (1 << i)) != 0) {
sum += arr[i];
}
}
return sum == targetSum;
}
// Find all subsets with given sum using bitmask
public List<List<Integer>> findSubsetsWithSum(int[] arr, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
int n = arr.length;
// Check all possible subsets
for (int mask = 0; mask < (1 << n); mask++) {
if (hasSubsetSum(arr, mask, targetSum)) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(arr[i]);
}
}
result.add(subset);
}
}
return result;
}
// Count number of ways to partition set into k non-empty subsets
public int countPartitions(int n, int k) {
// dp[mask][groups] = number of ways to partition elements in mask into groups subsets
int[][] dp = new int[1 << n][k + 1];
dp[0][0] = 1;
for (int mask = 0; mask < (1 << n); mask++) {
for (int groups = 0; groups <= k; groups++) {
if (dp[mask][groups] == 0) continue;
// Try adding a new subset
for (int subset = mask; subset < (1 << n); subset = (subset + 1) | mask) {
if (groups < k) {
dp[subset][groups + 1] += dp[mask][groups];
}
}
}
}
return dp[(1 << n) - 1][k];
}
// Traveling Salesman Problem using bitmask DP
public int tsp(int[][] dist) {
int n = dist.length;
int[][] dp = new int[1 << n][n];
// Initialize with infinity
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE);
}
dp[1][0] = 0; // Start from city 0
for (int mask = 0; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0 || dp[mask][u] == Integer.MAX_VALUE) {
continue;
}
for (int v = 0; v < n; v++) {
if (mask & (1 << v)) continue;
int newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
}
}
}
int result = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
if (dp[(1 << n) - 1][i] != Integer.MAX_VALUE) {
result = Math.min(result, dp[(1 << n) - 1][i] + dist[i][0]);
}
}
return result;
}
// Assignment problem using bitmask
public int minCostAssignment(int[][] cost) {
int n = cost.length;
int[] dp = new int[1 << n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == Integer.MAX_VALUE) continue;
int person = Integer.bitCount(mask);
if (person >= n) continue;
for (int task = 0; task < n; task++) {
if ((mask & (1 << task)) == 0) {
int newMask = mask | (1 << task);
dp[newMask] = Math.min(dp[newMask], dp[mask] + cost[person][task]);
}
}
}
return dp[(1 << n) - 1];
}
// Check if two sets represented by bitmasks are disjoint
public boolean areDisjoint(int mask1, int mask2) {
return (mask1 & mask2) == 0;
}
// Get complement of a set in universal set
public int getComplement(int mask, int universeSize) {
return ((1 << universeSize) - 1) ^ mask;
}
// Get all subsets of a given set
public List<Integer> getAllSubsets(int mask) {
List<Integer> subsets = new ArrayList<>();
for (int subset = mask; ; subset = (subset - 1) & mask) {
subsets.add(subset);
if (subset == 0) break;
}
return subsets;
}
// Check if one set is subset of another
public boolean isSubset(int subset, int superset) {
return (subset & superset) == subset;
}
}
6.2 Advanced Bitmasking Applications
// Advanced bitmasking for complex problems
public class AdvancedBitmasking {
// Maximum subset XOR
public int maxSubsetXOR(int[] arr) {
int maxXOR = 0;
int n = arr.length;
// Try all possible subsets
for (int mask = 1; mask < (1 << n); mask++) {
int xor = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
xor ^= arr[i];
}
}
maxXOR = Math.max(maxXOR, xor);
}
return maxXOR;
}
// Count number of subsets with XOR equal to target
public int countSubsetsWithXOR(int[] arr, int target) {
int count = 0;
int n = arr.length;
for (int mask = 0; mask < (1 << n); mask++) {
int xor = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
xor ^= arr[i];
}
}
if (xor == target) {
count++;
}
}
return count;
}
// Shortest Hamiltonian path using bitmask DP
public int shortestHamiltonianPath(int[][] graph) {
int n = graph.length;
int[][] dp = new int[1 << n][n];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE);
}
// Can start from any node
for (int i = 0; i < n; i++) {
dp[1 << i][i] = 0;
}
for (int mask = 0; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0 || dp[mask][u] == Integer.MAX_VALUE) {
continue;
}
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0 || graph[u][v] == 0) {
continue;
}
int newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + graph[u][v]);
}
}
}
int result = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
result = Math.min(result, dp[(1 << n) - 1][i]);
}
return result == Integer.MAX_VALUE ? -1 : result;
}
// Count number of ways to color graph with k colors (bitmask DP)
public int countGraphColorings(int[][] graph, int k) {
int n = graph.length;
// dp[mask][color] = ways to color vertices in mask with last vertex having color
int[][] dp = new int[1 << n][k];
// Base case: single vertex can be colored in k ways
for (int i = 0; i < n; i++) {
for (int color = 0; color < k; color++) {
dp[1 << i][color] = 1;
}
}
for (int mask = 1; mask < (1 << n); mask++) {
int vertices = Integer.bitCount(mask);
if (vertices == 1) continue;
for (int lastVertex = 0; lastVertex < n; lastVertex++) {
if ((mask & (1 << lastVertex)) == 0) continue;
int prevMask = mask ^ (1 << lastVertex);
for (int color = 0; color < k; color++) {
// Check if this color conflicts with adjacent vertices
boolean canUseColor = true;
for (int adj = 0; adj < n; adj++) {
if ((mask & (1 << adj)) != 0 && graph[lastVertex][adj] == 1) {
// Adjacent vertex exists in current mask
if (adj != lastVertex) {
// We need to ensure adjacent vertex doesn't have same color
// This is handled by considering all valid colorings of previous mask
}
}
}
if (canUseColor) {
for (int prevColor = 0; prevColor < k; prevColor++) {
// Check if prevColor conflicts with current color for adjacent vertices
boolean valid = true;
for (int adj = 0; adj < n; adj++) {
if ((prevMask & (1 << adj)) != 0 && graph[lastVertex][adj] == 1 &&
prevColor == color) {
valid = false;
break;
}
}
if (valid) {
dp[mask][color] += dp[prevMask][prevColor];
}
}
}
}
}
}
int result = 0;
for (int color = 0; color < k; color++) {
result += dp[(1 << n) - 1][color];
}
return result;
}
}
Pattern 7: XOR-Based Problems
7.1 XOR Properties and Applications
// XOR-based problem solving
public class XORProblems {
// Find missing number using XOR
public int findMissingNumber(int[] arr, int n) {
int xor1 = 0; // XOR of all elements in array
int xor2 = 0; // XOR of all numbers from 1 to n+1
for (int num : arr) {
xor1 ^= num;
}
for (int i = 1; i <= n + 1; i++) {
xor2 ^= i;
}
return xor1 ^ xor2;
}
// Swap two numbers without temporary variable
public void swapNumbers(int a, int b) {
System.out.println("Before: a = " + a + ", b = " + b);
if (a != b) { // Avoid swapping same memory location
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
System.out.println("After: a = " + a + ", b = " + b);
}
// Find two non-repeating elements in array
public int[] findTwoNonRepeating(int[] arr) {
int xor = 0;
// XOR all elements
for (int num : arr) {
xor ^= num;
}
// Find rightmost set bit
int rightmostSetBit = xor & (-xor);
int first = 0, second = 0;
// Divide elements into two groups
for (int num : arr) {
if ((num & rightmostSetBit) != 0) {
first ^= num;
} else {
second ^= num;
}
}
return new int[]{first, second};
}
// Maximum XOR of two numbers in array
public int findMaximumXOR(int[] nums) {
int maxXOR = 0;
int mask = 0;
// Build prefix mask bit by bit
for (int i = 30; i >= 0; i--) {
mask |= (1 << i);
Set<Integer> prefixes = new HashSet<>();
// Get all prefixes with current mask
for (int num : nums) {
prefixes.add(num & mask);
}
int candidate = maxXOR | (1 << i);
// Check if candidate is achievable
for (int prefix : prefixes) {
if (prefixes.contains(candidate ^ prefix)) {
maxXOR = candidate;
break;
}
}
}
return maxXOR;
}
// Count pairs with given XOR
public int countPairsWithXOR(int[] arr, int k) {
Map<Integer, Integer> freq = new HashMap<>();
int count = 0;
for (int num : arr) {
int complement = num ^ k;
if (freq.containsKey(complement)) {
count += freq.get(complement);
}
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
return count;
}
// XOR of all subarrays
public int xorOfAllSubarrays(int[] arr) {
int n = arr.length;
int result = 0;
for (int i = 0; i < n; i++) {
// Count frequency of arr[i] in all subarrays
int frequency = (i + 1) * (n - i);
// If frequency is odd, include arr[i] in result
if (frequency % 2 == 1) {
result ^= arr[i];
}
}
return result;
}
// Find XOR from L to R
public int xorInRange(int l, int r) {
return xorFromZero(r) ^ xorFromZero(l - 1);
}
private int xorFromZero(int n) {
if (n < 0) return 0;
int remainder = n % 4;
switch (remainder) {
case 0: return n;
case 1: return 1;
case 2: return n + 1;
case 3: return 0;
default: return 0;
}
}
// Check if array can be divided into pairs with equal XOR
public boolean canDivideIntoPairs(int[] arr) {
int xor = 0;
for (int num : arr) {
xor ^= num;
}
return xor == 0;
}
// Minimum XOR subarray
public int minXORSubarray(int[] arr) {
int n = arr.length;
int minXOR = Integer.MAX_VALUE;
// Try all subarrays
for (int i = 0; i < n; i++) {
int xor = 0;
for (int j = i; j < n; j++) {
xor ^= arr[j];
minXOR = Math.min(minXOR, xor);
}
}
return minXOR;
}
// Count subarrays with XOR equal to k
public int countSubarraysWithXOR(int[] arr, int k) {
Map<Integer, Integer> prefixXORCount = new HashMap<>();
prefixXORCount.put(0, 1);
int count = 0;
int xor = 0;
for (int num : arr) {
xor ^= num;
if (prefixXORCount.containsKey(xor ^ k)) {
count += prefixXORCount.get(xor ^ k);
}
prefixXORCount.put(xor, prefixXORCount.getOrDefault(xor, 0) + 1);
}
return count;
}
}
Pattern 8: Bit Shifting Patterns
8.1 Left and Right Shift Operations[8]
// Bit shifting operations and applications
public class BitShiftingPatterns {
// Multiply by power of 2 using left shift
public int multiplyByPowerOf2(int num, int power) {
return num << power; // num * (2^power)
}
// Divide by power of 2 using right shift
public int divideByPowerOf2(int num, int power) {
return num >> power; // num / (2^power)
}
// Check if number is divisible by power of 2
public boolean isDivisibleByPowerOf2(int num, int power) {
int divisor = 1 << power;
return (num & (divisor - 1)) == 0;
}
// Rotate bits left
public int rotateLeft(int num, int positions) {
positions %= 32; // Handle positions > 32
return (num << positions) | (num >>> (32 - positions));
}
// Rotate bits right
public int rotateRight(int num, int positions) {
positions %= 32;
return (num >>> positions) | (num << (32 - positions));
}
// Extract bits from position i to j
public int extractBits(int num, int i, int j) {
// Shift right to bring bits to least significant positions
int shifted = num >> i;
// Create mask for j-i+1 bits
int mask = (1 << (j - i + 1)) - 1;
return shifted & mask;
}
// Set bits from position i to j with given value
public int setBitsInRange(int num, int value, int i, int j) {
// Create mask to clear bits from i to j
int allOnes = ~0;
int left = allOnes << (j + 1);
int right = (1 << i) - 1;
int mask = left | right;
// Clear bits and set new value
return (num & mask) | (value << i);
}
// Arithmetic right shift (preserves sign)
public int arithmeticRightShift(int num, int positions) {
return num >> positions;
}
// Logical right shift (fills with zeros)
public int logicalRightShift(int num, int positions) {
return num >>> positions;
}
// Efficient modulo operation for powers of 2
public int modPowerOf2(int num, int power) {
int mask = (1 << power) - 1;
return num & mask; // Equivalent to num % (2^power)
}
// Check if shifting causes overflow
public boolean willLeftShiftOverflow(int num, int positions) {
if (positions >= 32) return true;
// Check if any bit in the top 'positions' bits is set
int mask = ~((1 << (32 - positions)) - 1);
return (num & mask) != 0;
}
// Circular shift left with overflow detection
public int circularShiftLeft(int num, int positions) {
positions %= 32;
return (num << positions) | (num >>> (32 - positions));
}
// Count number of positions to shift to make number odd
public int shiftToMakeOdd(int num) {
if (num == 0) return -1; // Cannot make 0 odd
int shifts = 0;
while ((num & 1) == 0) {
num >>= 1;
shifts++;
}
return shifts;
}
// Binary search using bit shifting
public int binarySearchWithShifting(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1); // (left + right) / 2
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Fast multiplication using bit shifting
public int fastMultiply(int a, int b) {
int result = 0;
while (b > 0) {
if ((b & 1) == 1) {
result += a;
}
a <<= 1; // a = a * 2
b >>= 1; // b = b / 2
}
return result;
}
// Generate powers of 2 using shifting
public List<Integer> generatePowersOf2(int maxPower) {
List<Integer> powers = new ArrayList<>();
for (int i = 0; i <= maxPower; i++) {
powers.add(1 << i);
}
return powers;
}
}
8.2 Advanced Shifting Applications
// Advanced applications of bit shifting
public class AdvancedShiftingApplications {
// Efficient square root using bit shifting
public int integerSquareRoot(int n) {
if (n < 2) return n;
int x = n;
// Newton's method with bit shifting optimization
while (x > n / x) {
x = (x + n / x) >> 1; // Divide by 2 using right shift
}
return x;
}
// Fast integer division using bit shifting
public int fastDivide(int dividend, int divisor) {
if (divisor == 0) throw new ArithmeticException("Division by zero");
boolean negative = (dividend < 0) ^ (divisor < 0);
long absDividend = Math.abs((long) dividend);
long absDivisor = Math.abs((long) divisor);
long result = 0;
while (absDividend >= absDivisor) {
long temp = absDivisor;
long count = 1;
while (absDividend >= (temp << 1)) {
temp <<= 1;
count <<= 1;
}
absDividend -= temp;
result += count;
}
if (negative) result = -result;
return (int) Math.max(Integer.MIN_VALUE, Math.min(Integer.MAX_VALUE, result));
}
// Check if number is power of 4 using shifting
public boolean isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}
// Convert decimal to binary using shifting
public String decimalToBinaryShifting(int n) {
if (n == 0) return "0";
StringBuilder binary = new StringBuilder();
while (n > 0) {
binary.append(n & 1);
n >>= 1;
}
return binary.reverse().toString();
}
// Find log base 2 using bit shifting
public int log2(int n) {
if (n <= 0) return -1;
int log = 0;
while ((n >>= 1) > 0) {
log++;
}
return log;
}
// Ceiling of log base 2
public int ceilLog2(int n) {
if (n <= 1) return 0;
int log = log2(n);
// If n is power of 2, return log, otherwise log + 1
return isPowerOfTwo(n) ? log : log + 1;
}
private boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// Efficient GCD using bit shifting
public int gcdBitShifting(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
// Count common factors of 2
int shift = 0;
while (((a | b) & 1) == 0) {
a >>= 1;
b >>= 1;
shift++;
}
// Remove factors of 2 from a
while ((a & 1) == 0) {
a >>= 1;
}
do {
// Remove factors of 2 from b
while ((b & 1) == 0) {
b >>= 1;
}
// Ensure a <= b
if (a > b) {
int temp = a;
a = b;
b = temp;
}
b -= a;
} while (b != 0);
return a << shift;
}
// Count set bits using shifting
public int countSetBitsShifting(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
// Generate Gray code using bit shifting
public List<Integer> generateGrayCode(int n) {
List<Integer> grayCode = new ArrayList<>();
for (int i = 0; i < (1 << n); i++) {
grayCode.add(i ^ (i >> 1));
}
return grayCode;
}
// Reverse Gray code
public int reverseGrayCode(int gray) {
int binary = 0;
while (gray != 0) {
binary ^= gray;
gray >>= 1;
}
return binary;
}
}
Pattern 9: Gray Code & Binary Representation
9.1 Gray Code Generation and Properties
// Gray code operations and binary representations
public class GrayCodeOperations {
// Generate Gray code sequence for n bits
public List<Integer> grayCode(int n) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < (1 << n); i++) {
result.add(i ^ (i >> 1)); // Convert binary to Gray code
}
return result;
}
// Generate Gray code as binary strings
public List<String> grayCodeStrings(int n) {
List<String> result = new ArrayList<>();
for (int i = 0; i < (1 << n); i++) {
int gray = i ^ (i >> 1);
String binaryString = String.format("%" + n + "s",
Integer.toBinaryString(gray)).replace(' ', '0');
result.add(binaryString);
}
return result;
}
// Convert binary to Gray code
public int binaryToGray(int binary) {
return binary ^ (binary >> 1);
}
// Convert Gray code to binary
public int grayToBinary(int gray) {
int binary = 0;
while (gray != 0) {
binary ^= gray;
gray >>= 1;
}
return binary;
}
// Generate Gray code using recursive approach
public List<String> grayCodeRecursive(int n) {
if (n == 0) {
return Arrays.asList("");
}
if (n == 1) {
return Arrays.asList("0", "1");
}
List<String> prevGrayCode = grayCodeRecursive(n - 1);
List<String> result = new ArrayList<>();
// First half: add '0' prefix to previous Gray codes
for (String code : prevGrayCode) {
result.add("0" + code);
}
// Second half: add '1' prefix to reversed previous Gray codes
for (int i = prevGrayCode.size() - 1; i >= 0; i--) {
result.add("1" + prevGrayCode.get(i));
}
return result;
}
// Find position of difference between consecutive Gray codes
public int findGrayCodeDifference(int gray1, int gray2) {
int diff = gray1 ^ gray2;
// Find position of the single set bit
return Integer.numberOfTrailingZeros(diff);
}
// Check if two numbers are consecutive in Gray code sequence
public boolean areConsecutiveGrayCodes(int a, int b) {
// Convert to Gray codes and check if they differ by exactly one bit
int grayA = binaryToGray(a);
int grayB = binaryToGray(b);
int diff = grayA ^ grayB;
// Check if diff is power of 2 (exactly one bit set)
return diff > 0 && (diff & (diff - 1)) == 0;
}
// Generate balanced Gray code (equal number of 0s and 1s in each position)
public List<String> balancedGrayCode(int n) {
// This is only possible for even n
if (n % 2 != 0) {
throw new IllegalArgumentException("Balanced Gray code requires even number of bits");
}
List<String> result = new ArrayList<>();
// Implementation would be more complex for true balanced Gray code
// This is a simplified version
return grayCodeStrings(n);
}
// Count transitions in Gray code sequence
public int countGrayCodeTransitions(int n) {
// Each transition changes exactly one bit
return (1 << n) - 1; // 2^n - 1 transitions for n-bit Gray code
}
// Generate modified Gray code with custom starting point
public List<Integer> customGrayCode(int n, int start) {
List<Integer> standardGray = grayCode(n);
List<Integer> result = new ArrayList<>();
// Find starting position
int startPos = standardGray.indexOf(start);
if (startPos == -1) {
throw new IllegalArgumentException("Invalid starting point");
}
// Rotate the sequence
for (int i = 0; i < standardGray.size(); i++) {
result.add(standardGray.get((i + startPos) % standardGray.size()));
}
return result;
}
// Check if a sequence follows Gray code property
public boolean isValidGrayCodeSequence(List<Integer> sequence) {
for (int i = 1; i < sequence.size(); i++) {
int diff = sequence.get(i - 1) ^ sequence.get(i);
// Check if exactly one bit is different
if (diff == 0 || (diff & (diff - 1)) != 0) {
return false;
}
}
return true;
}
// Find next Gray code in sequence
public int nextGrayCode(int current, int n) {
List<Integer> graySequence = grayCode(n);
int currentIndex = graySequence.indexOf(current);
if (currentIndex == -1) {
throw new IllegalArgumentException("Invalid Gray code");
}
return graySequence.get((currentIndex + 1) % graySequence.size());
}
}
9.2 Binary Representation Utilities
// Binary representation and manipulation utilities
public class BinaryRepresentationUtils {
// Get binary representation with leading zeros
public String toBinaryString(int num, int width) {
String binary = Integer.toBinaryString(num);
return String.format("%" + width + "s", binary).replace(' ', '0');
}
// Convert signed integer to binary (two's complement)
public String signedToBinary(int num) {
if (num >= 0) {
return toBinaryString(num, 32);
} else {
// For negative numbers, Java's toBinaryString already gives two's complement
return Integer.toBinaryString(num);
}
}
// Parse binary string to integer
public int parseBinary(String binary) {
return Integer.parseInt(binary, 2);
}
// Count hamming distance between two numbers
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
// Total hamming distance for all pairs in array
public int totalHammingDistance(int[] nums) {
int total = 0;
int n = nums.length;
// For each bit position
for (int i = 0; i < 32; i++) {
int countOnes = 0;
// Count how many numbers have bit i set
for (int num : nums) {
if ((num & (1 << i)) != 0) {
countOnes++;
}
}
// Hamming distance contribution for bit i
total += countOnes * (n - countOnes);
}
return total;
}
// Check if binary representation is palindrome
public boolean isBinaryPalindrome(int num) {
String binary = Integer.toBinaryString(num);
String reversed = new StringBuilder(binary).reverse().toString();
return binary.equals(reversed);
}
// Find longest run of 1s in binary representation
public int longestRunOfOnes(int num) {
int maxRun = 0;
int currentRun = 0;
while (num != 0) {
if ((num & 1) == 1) {
currentRun++;
maxRun = Math.max(maxRun, currentRun);
} else {
currentRun = 0;
}
num >>= 1;
}
return maxRun;
}
// Find longest run of 0s in binary representation
public int longestRunOfZeros(int num) {
// Invert the number and find longest run of 1s
return longestRunOfOnes(~num);
}
// Count number of bit flips needed to convert a to b
public int bitFlipsToConvert(int a, int b) {
return Integer.bitCount(a ^ b);
}
// Generate all binary strings of length n
public List<String> generateBinaryStrings(int n) {
List<String> result = new ArrayList<>();
for (int i = 0; i < (1 << n); i++) {
result.add(toBinaryString(i, n));
}
return result;
}
// Generate all binary strings with exactly k ones
public List<String> generateBinaryStringsWithKOnes(int n, int k) {
List<String> result = new ArrayList<>();
for (int i = 0; i < (1 << n); i++) {
if (Integer.bitCount(i) == k) {
result.add(toBinaryString(i, n));
}
}
return result;
}
// Check if binary string has alternating pattern
public boolean hasAlternatingPattern(String binary) {
for (int i = 1; i < binary.length(); i++) {
if (binary.charAt(i) == binary.charAt(i - 1)) {
return false;
}
}
return true;
}
// Generate next lexicographic binary string
public String nextBinaryString(String binary) {
int num = parseBinary(binary);
num++;
return toBinaryString(num, binary.length());
}
// Find binary string with maximum decimal value using k flips
public String maxBinaryWithKFlips(String binary, int k) {
char[] chars = binary.toCharArray();
for (int i = 0; i < chars.length && k > 0; i++) {
if (chars[i] == '0') {
chars[i] = '1';
k--;
}
}
// If k is still positive and even, we can flip back and forth
// If k is odd, flip the rightmost 1 to 0
if (k > 0 && k % 2 == 1) {
for (int i = chars.length - 1; i >= 0; i--) {
if (chars[i] == '1') {
chars[i] = '0';
break;
}
}
}
return new String(chars);
}
}
Pattern 10: Advanced Bit Manipulation
10.1 Complex Bit Operations
// Advanced bit manipulation techniques
public class AdvancedBitManipulation {
// Sparse number operations
public int nextSparseNumber(int n) {
// A sparse number has no two adjacent bits set
List<Integer> binary = new ArrayList<>();
// Convert to binary array
while (n > 0) {
binary.add(n & 1);
n >>= 1;
}
// Scan from second bit to check for adjacent 1s
for (int i = 1; i < binary.size(); i++) {
if (binary.get(i) == 1 && binary.get(i - 1) == 1) {
// Found adjacent 1s
// Make all bits after position i equal to 0
for (int j = 0; j < i; j++) {
binary.set(j, 0);
}
// Find next position to set
int pos = i;
while (pos < binary.size() && binary.get(pos) == 1) {
binary.set(pos, 0);
pos++;
}
if (pos == binary.size()) {
binary.add(1);
} else {
binary.set(pos, 1);
}
break;
}
}
// Convert back to decimal
int result = 0;
for (int i = 0; i < binary.size(); i++) {
result += binary.get(i) * (1 << i);
}
return result;
}
// Check if number has alternating bits
public boolean hasAlternatingBits(int n) {
int prev = n & 1;
n >>= 1;
while (n > 0) {
int curr = n & 1;
if (curr == prev) {
return false;
}
prev = curr;
n >>= 1;
}
return true;
}
// Binary string with substrings representing 1 to N
public String binaryStringWithSubstrings(int n) {
// This is a complex problem - simplified implementation
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
String binary = Integer.toBinaryString(i);
if (sb.length() == 0 || sb.indexOf(binary) == -1) {
sb.append(binary);
}
}
return sb.toString();
}
// Minimum number of flips to make binary string alternating
public int minFlipsToAlternating(String s) {
int flips1 = 0; // Starting with '0'
int flips2 = 0; // Starting with '1'
for (int i = 0; i < s.length(); i++) {
char expected1 = (i % 2 == 0) ? '0' : '1';
char expected2 = (i % 2 == 0) ? '1' : '0';
if (s.charAt(i) != expected1) flips1++;
if (s.charAt(i) != expected2) flips2++;
}
return Math.min(flips1, flips2);
}
// Count number of 1 bits you need to flip to get longest sequence of 1s
public int findLengthWithFlip(int num, int flips) {
int left = 0, right = 0;
int zerosCount = 0;
int maxLength = 0;
// Convert to binary array for easier processing
List<Integer> bits = new ArrayList<>();
int temp = num;
while (temp > 0) {
bits.add(temp & 1);
temp >>= 1;
}
Collections.reverse(bits);
while (right < bits.size()) {
if (bits.get(right) == 0) {
zerosCount++;
}
while (zerosCount > flips) {
if (bits.get(left) == 0) {
zerosCount--;
}
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
// Bitwise AND of range [left, right]
public int rangeBitwiseAnd(int left, int right) {
int shift = 0;
// Find common prefix
while (left != right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
// Count number of bit differences in all pairs
public int sumOfBitDifferences(int[] arr) {
int sum = 0;
int n = arr.length;
// For each bit position
for (int i = 0; i < 32; i++) {
int count = 0;
// Count numbers with bit i set
for (int num : arr) {
if ((num & (1 << i)) != 0) {
count++;
}
}
// Add contribution of this bit position
sum += count * (n - count) * 2;
}
return sum;
}
// Maximum product of word lengths where words don't share common letters
public int maxProduct(String[] words) {
int n = words.length;
int[] masks = new int[n];
// Create bit mask for each word
for (int i = 0; i < n; i++) {
for (char c : words[i].toCharArray()) {
masks[i] |= 1 << (c - 'a');
}
}
int maxProd = 0;
// Check all pairs
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) == 0) {
maxProd = Math.max(maxProd, words[i].length() * words[j].length());
}
}
}
return maxProd;
}
// Flip bits to convert A to B
public int convertAtoB(int a, int b) {
int diff = a ^ b;
return Integer.bitCount(diff);
}
// Find complement of number in given range
public int findComplement(int num) {
// Find number of bits in num
int bitLength = Integer.toBinaryString(num).length();
// Create mask with all 1s of same length
int mask = (1 << bitLength) - 1;
return num ^ mask;
}
}
Pattern 11: Optimization with Bits
11.1 Space and Time Optimizations
// Using bit manipulation for optimization
public class BitOptimizations {
// Sieve of Eratosthenes using bit manipulation
public List<Integer> sieveOfEratosthenes(int n) {
// Use bit array to save space
int[] primes = new int[(n + 31) / 32]; // Each int stores 32 bits
// Set all bits to 1 initially (assume all are prime)
Arrays.fill(primes, -1); // All bits set
// Clear bit for 0 and 1
clearBit(primes, 0);
clearBit(primes, 1);
for (int i = 2; i * i <= n; i++) {
if (getBit(primes, i)) {
for (int j = i * i; j <= n; j += i) {
clearBit(primes, j);
}
}
}
List<Integer> result = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (getBit(primes, i)) {
result.add(i);
}
}
return result;
}
private boolean getBit(int[] arr, int index) {
int intIndex = index / 32;
int bitIndex = index % 32;
return (arr[intIndex] & (1 << bitIndex)) != 0;
}
private void clearBit(int[] arr, int index) {
int intIndex = index / 32;
int bitIndex = index % 32;
arr[intIndex] &= ~(1 << bitIndex);
}
// Counting sort for small range using bit manipulation
public void countingSortBitwise(int[] arr, int maxVal) {
// Use bit array for counting
int[] count = new int[(maxVal + 31) / 32];
// Set bits for present elements
for (int num : arr) {
setBitInArray(count, num);
}
// Reconstruct array
int index = 0;
for (int i = 0; i <= maxVal; i++) {
while (getBitInArray(count, i)) {
arr[index++] = i;
clearBitInArray(count, i);
}
}
}
private void setBitInArray(int[] arr, int index) {
arr[index / 32] |= (1 << (index % 32));
}
private boolean getBitInArray(int[] arr, int index) {
return (arr[index / 32] & (1 << (index % 32))) != 0;
}
private void clearBitInArray(int[] arr, int index) {
arr[index / 32] &= ~(1 << (index % 32));
}
// Fast set operations using bit manipulation
public static class BitSet {
private long[] bits;
private int size;
public BitSet(int maxSize) {
this.size = maxSize;
this.bits = new long[(maxSize + 63) / 64];
}
public void set(int index) {
bits[index / 64] |= (1L << (index % 64));
}
public void clear(int index) {
bits[index / 64] &= ~(1L << (index % 64));
}
public boolean get(int index) {
return (bits[index / 64] & (1L << (index % 64))) != 0;
}
public BitSet union(BitSet other) {
BitSet result = new BitSet(Math.max(this.size, other.size));
for (int i = 0; i < result.bits.length; i++) {
if (i < this.bits.length && i < other.bits.length) {
result.bits[i] = this.bits[i] | other.bits[i];
} else if (i < this.bits.length) {
result.bits[i] = this.bits[i];
} else if (i < other.bits.length) {
result.bits[i] = other.bits[i];
}
}
return result;
}
public BitSet intersection(BitSet other) {
BitSet result = new BitSet(Math.max(this.size, other.size));
for (int i = 0; i < Math.min(this.bits.length, other.bits.length); i++) {
result.bits[i] = this.bits[i] & other.bits[i];
}
return result;
}
public int cardinality() {
int count = 0;
for (long bit : bits) {
count += Long.bitCount(bit);
}
return count;
}
}
// Fast duplicate detection using bit manipulation
public boolean hasDuplicates(int[] arr, int maxVal) {
if (maxVal >= 32 * 1000000) { // Too large for bit array
return hasDuplicatesHashSet(arr);
}
int[] bitArray = new int[(maxVal + 31) / 32];
for (int num : arr) {
if (getBitInArray(bitArray, num)) {
return true; // Duplicate found
}
setBitInArray(bitArray, num);
}
return false;
}
private boolean hasDuplicatesHashSet(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
if (!seen.add(num)) {
return true;
}
}
return false;
}
// Compress boolean array using bit manipulation
public int[] compressBooleanArray(boolean[] boolArray) {
int[] compressed = new int[(boolArray.length + 31) / 32];
for (int i = 0; i < boolArray.length; i++) {
if (boolArray[i]) {
compressed[i / 32] |= (1 << (i % 32));
}
}
return compressed;
}
public boolean[] decompressBooleanArray(int[] compressed, int originalSize) {
boolean[] decompressed = new boolean[originalSize];
for (int i = 0; i < originalSize; i++) {
decompressed[i] = (compressed[i / 32] & (1 << (i % 32))) != 0;
}
return decompressed;
}
// Efficient subset enumeration
public void enumerateSubsets(int set, Consumer<Integer> processor) {
// Enumerate all subsets of 'set'
for (int subset = set; ; subset = (subset - 1) & set) {
processor.accept(subset);
if (subset == 0) break;
}
}
// Fast population count for arrays
public int totalPopulationCount(int[] arr) {
int total = 0;
for (int num : arr) {
total += Integer.bitCount(num);
}
return total;
}
}
Pattern 12: Real-World Applications
12.1 Practical Bit Manipulation Applications
// Real-world applications of bit manipulation
public class RealWorldBitApplications {
// File permission system (Unix-style)
public static class FilePermissions {
private int permissions;
// Permission constants
public static final int OWNER_READ = 1 << 8; // 400
public static final int OWNER_WRITE = 1 << 7; // 200
public static final int OWNER_EXECUTE = 1 << 6; // 100
public static final int GROUP_READ = 1 << 5; // 040
public static final int GROUP_WRITE = 1 << 4; // 020
public static final int GROUP_EXECUTE = 1 << 3; // 010
public static final int OTHER_READ = 1 << 2; // 004
public static final int OTHER_WRITE = 1 << 1; // 002
public static final int OTHER_EXECUTE = 1; // 001
public FilePermissions(int permissions) {
this.permissions = permissions;
}
public boolean hasPermission(int permission) {
return (permissions & permission) != 0;
}
public void grantPermission(int permission) {
permissions |= permission;
}
public void revokePermission(int permission) {
permissions &= ~permission;
}
public String toOctalString() {
return Integer.toOctalString(permissions);
}
public String toReadableString() {
StringBuilder sb = new StringBuilder();
// Owner permissions
sb.append(hasPermission(OWNER_READ) ? 'r' : '-');
sb.append(hasPermission(OWNER_WRITE) ? 'w' : '-');
sb.append(hasPermission(OWNER_EXECUTE) ? 'x' : '-');
// Group permissions
sb.append(hasPermission(GROUP_READ) ? 'r' : '-');
sb.append(hasPermission(GROUP_WRITE) ? 'w' : '-');
sb.append(hasPermission(GROUP_EXECUTE) ? 'x' : '-');
// Other permissions
sb.append(hasPermission(OTHER_READ) ? 'r' : '-');
sb.append(hasPermission(OTHER_WRITE) ? 'w' : '-');
sb.append(hasPermission(OTHER_EXECUTE) ? 'x' : '-');
return sb.toString();
}
}
// Network subnet calculator using bit manipulation
public static class SubnetCalculator {
public static class SubnetInfo {
public String networkAddress;
public String broadcastAddress;
public String subnetMask;
public int hostCount;
public String firstHost;
public String lastHost;
}
public SubnetInfo calculateSubnet(String ip, int prefixLength) {
int ipInt = ipToInt(ip);
int subnetMask = (-1) << (32 - prefixLength);
int networkAddress = ipInt & subnetMask;
int broadcastAddress = networkAddress | (~subnetMask);
SubnetInfo info = new SubnetInfo();
info.networkAddress = intToIp(networkAddress);
info.broadcastAddress = intToIp(broadcastAddress);
info.subnetMask = intToIp(subnetMask);
info.hostCount = (1 << (32 - prefixLength)) - 2; // Exclude network and broadcast
info.firstHost = intToIp(networkAddress + 1);
info.lastHost = intToIp(broadcastAddress - 1);
return info;
}
private int ipToInt(String ip) {
String[] parts = ip.split("\\.");
return (Integer.parseInt(parts[0]) << 24) |
(Integer.parseInt(parts[1]) << 16) |
(Integer.parseInt(parts[2]) << 8) |
Integer.parseInt(parts[3]);
}
private String intToIp(int ip) {
return ((ip >> 24) & 0xFF) + "." +
((ip >> 16) & 0xFF) + "." +
((ip >> 8) & 0xFF) + "." +
(ip & 0xFF);
}
}
// Flag system for application settings
public static class ApplicationFlags {
private long flags;
// Feature flags
public static final long DARK_MODE = 1L << 0;
public static final long NOTIFICATIONS = 1L << 1;
public static final long AUTO_SAVE = 1L << 2;
public static final long SPELL_CHECK = 1L << 3;
public static final long SYNTAX_HIGHLIGHTING = 1L << 4;
public static final long LINE_NUMBERS = 1L << 5;
public static final long WORD_WRAP = 1L << 6;
public static final long AUTO_INDENT = 1L << 7;
// ... up to 64 flags
public void enableFlag(long flag) {
flags |= flag;
}
public void disableFlag(long flag) {
flags &= ~flag;
}
public boolean isFlagEnabled(long flag) {
return (flags & flag) != 0;
}
public void toggleFlag(long flag) {
flags ^= flag;
}
public long getAllFlags() {
return flags;
}
public void setAllFlags(long flags) {
this.flags = flags;
}
public int getEnabledFlagCount() {
return Long.bitCount(flags);
}
}
// Database indexing using bit manipulation
public static class BitIndex {
private Map<String, BitSet> columnIndexes;
public BitIndex() {
columnIndexes = new HashMap<>();
}
public void createIndex(String column, List<Object> values) {
Set<Object> uniqueValues = new HashSet<>(values);
for (Object value : uniqueValues) {
BitSet bitSet = new BitSet(values.size());
for (int i = 0; i < values.size(); i++) {
if (values.get(i).equals(value)) {
bitSet.set(i);
}
}
columnIndexes.put(column + ":" + value, bitSet);
}
}
public BitSet query(String column, Object value) {
return columnIndexes.get(column + ":" + value);
}
public BitSet intersect(BitSet... bitSets) {
if (bitSets.length == 0) return new BitSet();
BitSet result = (BitSet) bitSets[0].clone();
for (int i = 1; i < bitSets.length; i++) {
result.and(bitSets[i]);
}
return result;
}
public BitSet union(BitSet... bitSets) {
if (bitSets.length == 0) return new BitSet();
BitSet result = (BitSet) bitSets[0].clone();
for (int i = 1; i < bitSets.length; i++) {
result.or(bitSets[i]);
}
return result;
}
}
// Bloom filter implementation
public static class BloomFilter {
private BitSet bitSet;
private int size;
private int hashFunctions;
public BloomFilter(int size, int hashFunctions) {
this.size = size;
this.hashFunctions = hashFunctions;
this.bitSet = new BitSet(size);
}
public void add(String item) {
for (int i = 0; i < hashFunctions; i++) {
int hash = hash(item, i) % size;
if (hash < 0) hash += size;
bitSet.set(hash);
}
}
public boolean mightContain(String item) {
for (int i = 0; i < hashFunctions; i++) {
int hash = hash(item, i) % size;
if (hash < 0) hash += size;
if (!bitSet.get(hash)) {
return false;
}
}
return true;
}
private int hash(String item, int seed) {
int hash = seed;
for (char c : item.toCharArray()) {
hash = hash * 31 + c;
}
return hash;
}
public double getFalsePositiveRate() {
int setBits = bitSet.cardinality();
return Math.pow(1.0 - Math.exp(-hashFunctions * setBits / (double) size), hashFunctions);
}
}
}
Time & Space Complexity Reference
| Operation | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Basic Bit Ops | O(1) | O(1) | AND, OR, XOR, NOT, shifts |
| Count Set Bits | O(log n) | O(1) | Brian Kernighan's algorithm |
| Check Power of 2 | O(1) | O(1) | n & (n-1) == 0 |
| Generate Subsets | O(2^n) | O(2^n) | All possible combinations |
| XOR All Elements | O(n) | O(1) | Linear scan |
| Bitmasking DP | O(n × 2^m) | O(2^m) | m = number of items in mask |
| Sieve with Bits | O(n log log n) | O(n/32) | Space optimized sieve |
| Bloom Filter | O(k) | O(m/8) | k = hash functions, m = bits |